#include <bits/stdc++.h>

using namespace std;

// 买卖股票的最佳时机
// 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格
// 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票
// 设计一个算法来计算你所能获取的最大利润
// 返回你可以从这笔交易中获取的最大利润
// 如果你不能获取任何利润，返回 0
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int ans = 0;
        for(int i = 1, mn = prices[0]; i < prices.size(); ++i)
        {
            // mn : 0...i范围上的最小值
            mn = min(mn, prices[i]);
            ans = max(ans, prices[i] - mn);
        }
        return ans;
    }
};


class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        int f[n], g[n];
        // f[i] : 最多进行一次股票交易，此时持有股票的最大利润
        // g[i] : 最多进行一次股票交易，此时不持有股票的最大利润
        // 股票卖出时，则认为完成了一次股票交易
        f[0] = -prices[0], g[0] = 0;
        for(int i = 1; i < n; ++i)
        {
            f[i] = max(-prices[i], f[i - 1]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i]);
        }
        return g[n - 1];
    }
};